\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm,epsfig}
\usepackage[left=1in,top=1in,right=1in,bottom=1in,nohead]{geometry}
%\usepackage{fullpage}
\usepackage{subfigure}
\usepackage{times}
\usepackage{url}


\begin{document}

\input{macros}


\title{Cobra-analysis using meta-markov chains}


\author{Scott Roche}
\date{}
 
\maketitle

\section{Introduction}
The purpose of this document is to lay out the general idea behind the use of a "meta" Markov chain to study cobra walks and to state what we know so far, what seems likely (in terms of provability), and where the gaps are.

\subsection{An alternate way of viewing cobra-walks}

So far we have looked at cobra walks as a process in which a changing number of pebbles occupied the vertices of a graph $G$. Each step's configuration (i.e. the vertices that possessed a pebble, the active set) through a random process gives rise to the next step's configuration. Analysis therefore relies on keeping track of the number of pebbles at each step, the number of collisions that occur while moving to the next step, and the growth in the size of the active set.  The coalescing part of the process, the edge selection process of each vertex, and the underlying structure of the graph make it difficult to apply known results about random walks (stationary distributions, spectral properties, mixing times, and so on).

However, we can also view a cobra walk on $G$ as a simple random walk, albeit on a different graph (although one derived from $G$). In this new graph, which we will call $M_G$, the state space/vertex set is the $2^n -1$ non-empty subsets of $V(G)$, for $|V| = n$. Each vertex of $M_G$ represents one configuration of the cobra walk (i.e. which subset of $V(G)$ is active). The edges of $M_G$, for which we will give an explicit generation process shortly, are the transitions from one state in the cobra-process to another. An edge exists between two vertices of $M_G$ if and only if the pebbles of the active set in the corresponding cobra-walk state of $G$ can form the appropriate configuration at the incident edge in $M_G$. 

Why might this alternate view be useful? After all, $M_G$ has an exponentially-sized vertex and edge set, which would seem to make analysis even more difficult. Indeed, previous researches, when studying similar problems [INSERT GANESH REFERENCE HERE] have mentioned the existence of this meta-chain but have written off analyzing it. 

We believe that $M_G$ may offer an opportunity for \textit{easier} analysis. Even though we are dealing with exponentially large (in $n$) set sizes, we can still easily calculate the stationary distribution of the walk, as well as the probability of covering any vertex of $G$ at stationarity. 

\subsection{Overview of contents of document}


\section{Formal definition of $M_G$}

Here we formally define the vertex set of $M_G$ through a mapping function from $G$ to $M_G$, and the edge set of $M_G$ by using the tensor product chain of one-step of multiple independent random walks on G. 

\begin{definition} $V(M_G)$, the vertex set of $M_G$. 

Define a mapping $f: V(G) \rightarrow \{0,1\}^n$. For every $S \subseteq V(G)$ s.t. $S \neq \emptyset$, $f(S)$ equals an n-bit vector were the $i^{th}$ position of  $f(S) = 1$ if vertex $i \in S$ and 0 otherwise.  Then $V(M_G) = \text{Codomain}(f)$. 

\end{definition}

Before we define the edge set of $M_G$, we need to introduce a concept known as a \textit{tensor product chain}, and we will do this through an example. Consider a cobra walk with branching factor 2 on G at some state such that $S \subseteq V(G)$ is the set of active vertices (those that contain pebbles). Let $|S| = k$. To get to the next state in the cobra walk, we can view the walk as $2k$ independent random walks (with two pebbles at each of the nodes in $S$). Of course, since in the cobra-walk we are only tracking \textit{which} vertices are active at each step, there are (possibly) multiple ways of generating one configuration from another. We will address this shortly -- for now imagine we are just dealing with $2k$ independent random walks, as described, for one step.  Just like we created a meta-chain for the cobra-walk, $M_G$, we can also create one for our one-step walks, although instead of an exponential size graph we have what amounts to a Cartesian product of $2k$ copies of $G$.  Following Cooper [INSERT COOPER REFERENCE HERE], we label this graph $Q = Q_{2k}$. The vertex set of $Q_{2k}$ is $V(Q) = V^{2k}$, where a vertex $\mathbf{v} \in V(Q)$ is a $2k$-tuple $\mathbf{v} = (v_1,\ldots,v_{2k})$ of vertices $v_i \in V(G)$, with repeats allowed. Let $u_1, \ldots, u_{2k}$  be the starting positions of $2k$ independent random walks on $G$, and let $\textbf{u} = (u_1,\ldots,u_{2k})$ be the corresponding starting vertex in $Q_k$. 


\section{Stationary Distribution of $M_G$ and of important subsets of $M_G$}

Because the walk on $M_G$ is reversible (do we need to prove this?), we can express the stationary distribution in the standard way, for any vertex $i$, $\pi_i = \frac{d(i)}{2 E(M_G)}$. For the walk on $M_G$, what are these values? Let's start with the numerator. Note from the explicit construction of the edge set of $M_G$, there are a total of $d$ edges for each copy of the graph $G$ in the tensor product, thus there are $d^{2k}$ edges for each vertex $i$ that has density $k$. These edges are preserved under the contraction operation from $W_G(i)$ to $M_G(i)$, so the number of edges is preserved at each vertex of $M_G$. 

For the denominator, we want to count up all of the total edges. To do this, note there are $\binom{n}{k}$ vertices of density $k$, and thus $\binom{n}{k} d^{2k}$ edges that are incident to vertices of density $k$. Summing up over $k \in {0,1,\ldots,n}$, we have:
\begin{equation*}
d(V_{M_G}) =  \sum_{k = 0}^{n} \binom{n}{k} d^{2k}  = \sum_{k = 0}^{n} \binom{n}{k} (d^2)^k = (1 + d^2)^n
\end{equation*}  
making use of the ordinary generating function for the binomial sequence. (Note that we are off by a factor of one, since we include the case were $k=0$, and this vertex does not arise in $M_G$, but this quantity can be ignored). Thus, for any vertex $i$  of $M_G$ with density $k$, the random walk has stationary distribution:
\begin{equation}
 \pi_i = \frac{d^{2k}}{(1+d^2)^n}
\end{equation}
As is to be expected from a stationary distribution, $\pi_i$ for all $i$ depends only on the degree of $i$ and not any other properties of the graph (such as expansion). 

Clearly, for any individual vertex of $M_G$, the value of $\pi_i$ will be very low, given the size of the denominator.  In order to argue (for expanders, at least), that the mixing and cover times are fast, we will instead look at sets $A \subseteq V_{M_G}$ ask for $A$'s mass at stationarity, $\pi(A)$. 

Let's look at sets that will be needed for our cover-time proof. Define set $A_i$ to be: $\{v \in V_{M_G}  \text{ s.t. } i \in f^{-1}(A_i)\}$ In plain English, $A_i$ is the set of all vertices of $M_G$ the correspond to vertex $i$ of $V(G)$ being present in a configuration of the cobra walk.  What is the size of set $A_i$? (It should be clear that each $A_i$ is the same size for all $i$). 

\begin{lemma} 
For all $i \in V(G)$, $\pi(A_i) = \frac{d^2}{1 + d^2}$. 
\end{lemma}

\begin{proof}
The total degree of the vertices in $A_i$ is given by the sum
\begin{eqnarray*}
d(A_i) &=& d^2 + \binom{n-1}{2}d^4 + \binom{n-1}{3}d^4 + \ldots + \binom{n-1}{n-1}(d^2)^n \\
&=& \sum_{k=0}^{n-1} \binom{n-1}{k} (d^2)^{k+1} \\
&=& d^2 \sum_{k=0}^{n-1} \binom{n-1}{k} (d^2)^k \\
&=& d^2 (1 + d^2)^{n-1}
\end{eqnarray*}
Where the summation from $k=0$ to $n-1$ comes about because of the definition of $A_i$. Thus, 
\begin{equation*}
\pi(A_i) = \frac{d^2 (1 + d^2)^{n-1}}{(1 + d^2)^n} = \frac{d^2}{1+d^2} 
\end{equation*}
\end{proof}
So, as we can see, this is a fairly large probability, though it does not quite give us the high probability that we will need below.

Next, to show that the random walk on $M_G$ mixes very rapidly, we will need to look at sets $B_k$ of density $k$. These are all the vertices in $M_G$ that correspond to k active nodes in the cobra-walk on $G$. It should be immediately clear what $\pi(B_k)$ is:

\begin{lemma}
The stationary mass of set $B_k$ is given by $\pi(B_k) = \frac{ \binom{n}{k} d^{2k}}{(1 + d^2)^n}$. 
\end{lemma}

What does this tell us? First, I would like to mention some simulation results. When we simulated the cobra-walk on the d-regular random graph, and also on a clique, it turned out that the size of the active set hovered tightly in equilibrium around a saturation level of between .7 and .8 of the vertices, depending on the degree d. This provides experimental evidence for a tightly concentrated stationary distribution. 

Similarly, when plot the stationary distribution calculated above as a function of density (as in the figure below),  we again see a tight clump around a high density, with near-zero probability everywhere else. Using the formula in Lemma 3, it should be possible to show that with high probability, when you sample from the walk on $M_G$ at stationarity, the vertex sampled has density within some narrow interval $[a_1,a_2]$ in which every vertex in $M_G$ has some high density, let's say $\epsilon_1 n$,  for $\epsilon_1 \in [0.5,1)$.  This is stated formally in the conjecture section, although the evidence presented here, even though it is visual, is stronger than experimental evidence. Note that in the figure we have a 3-regular graph and 150 vertices, which represents the upper ability of the software I am using to calculate the stationary distribution.
\begin{figure}[1]
  \centering
  \setlength{\unitlength}{\textwidth} 
    \begin{picture}(1,0.5)%in case your image is twice as wide as it is high
                          %(otherwise change the 0.5 to your file's height/width).
       \put(-0.1,0){\includegraphics[width=1.2\unitlength]{stat_plot.pdf}}
    \end{picture}
\end{figure}


\section{A Mixing-time result for $M_G$}

Here we are going to provide a proof that the a cobra walk on an expander of the type outlined in Phase I of our original paper mixes in $\log n$ time. The only result we will reuse from this is that the cobra-walk, after $O(\log n)$ steps, has an active set of size $\epsilon_2 n$. The more important result that we will use comes from [INSERT REF TO PERES AND SOUSI HERE], and requires few preliminary definitions. 




\section{Conjectures awaiting proof}





\end{document}
